#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#include "imbus_internal.h"
#include "im_hash.h"

#define HASH_TABLE_MIN_SIZE 11
#define HASH_TABLE_MAX_SIZE 13845163

typedef struct _IMHashNode      IMHashNode;

struct _IMHashNode
{
    IMPointer        key;
    IMPointer        value;
    IMHashNode      *next;
};

struct _IMHashTable
{
    IMInt             size;
    IMInt             nnodes;
    IMHashNode      **nodes;
    IMHashFunc        hash_func;

    IMEqualFunc       key_equal_func;

    IMDestroyFunc     key_destroy_func;
    IMDestroyFunc     value_destroy_func;
};

struct _IMHashIterator
{
    IMHashTable      *table;
    IMHashNode      **head;
    IMHashNode      **node;
    IMHashNode      **next_node;
    IMInt             nnodes;
};

#define IM_HASH_TABLE_RESIZE(hash_table)                    \
    do {                                                    \
        if ((hash_table->size >= 3 * hash_table->nnodes &&  \
             hash_table->size > HASH_TABLE_MIN_SIZE) ||     \
            (3 * hash_table->size <= hash_table->nnodes &&  \
             hash_table->size < HASH_TABLE_MAX_SIZE))       \
            im_hash_table_resize (hash_table);              \
    } while (0)

/************************** Declaration of internal functions **********************/
static void             im_hash_table_resize        (IMHashTable        *hash_table);
static IMHashNode**     im_hash_table_lookup_node   (const IMHashTable  *hash_table,
                                                     IMConstPointer      key);
static IMHashNode*      im_hash_node_new            (IMPointer           key,
                                                     IMPointer           value);
static void             im_hash_node_destroy        (IMHashNode         *hash_node,
                                                     IMDestroyFunc       key_destroy_func,
                                                     IMDestroyFunc       value_destroy_func);
static void             im_hash_nodes_destroy       (IMHashNode         *hash_node,
                                                     IMDestroyFunc       key_destroy_func,
                                                     IMDestroyFunc       value_destroy_func);
static IMUInt im_hash_table_foreach_remove_or_steal (IMHashTable        *hash_table,
                                                     IMHRFunc            func,
                                                     IMPointer           user_data,
                                                     IMBool              destroy);

/****************************** Public functions **************************/

IMHashTable*
im_hash_table_new (IMHashFunc hash_func, IMEqualFunc key_equal_func)
{
    return im_hash_table_new_full (hash_func, key_equal_func, 0, 0);
}
IMHashTable*
im_hash_table_new_full (IMHashFunc      hash_func,
                        IMEqualFunc     key_equal_func,
                        IMDestroyFunc   key_destroy_func,
                        IMDestroyFunc   value_destroy_func)
{
    IMHashTable *hash_table;
  
    hash_table                      = im_slice_new (IMHashTable);
    hash_table->size                = HASH_TABLE_MIN_SIZE;
    hash_table->nnodes              = 0;
    hash_table->hash_func           = hash_func ? hash_func : im_direct_hash;
    hash_table->key_equal_func      = key_equal_func;
    hash_table->key_destroy_func    = key_destroy_func;
    hash_table->value_destroy_func  = value_destroy_func;
    hash_table->nodes               = im_new0 (IMHashNode*, hash_table->size);

    return hash_table;
}
void
im_hash_table_destroy (IMHashTable *hash_table)
{
    IMInt i;

    _im_return_if_fail (hash_table);

    for (i = 0; i < hash_table->size; ++i)
        im_hash_nodes_destroy (hash_table->nodes[i], 
                               hash_table->key_destroy_func,
                               hash_table->value_destroy_func);

    im_free (hash_table->nodes);
    im_slice_delete (IMHashTable, hash_table);
}
void
im_hash_table_insert (IMHashTable *hash_table, IMPointer key, IMPointer value)
{
    IMHashNode **node;
  
    _im_return_if_fail (hash_table);

    node = im_hash_table_lookup_node (hash_table, key);

    if (*node) {
        /* do not reset node->key in this place, keeping
         * the old key is the intended behaviour. 
         * im_hash_table_replace() can be used instead.
         */

        /* free the passed key */
        if (hash_table->key_destroy_func)
            hash_table->key_destroy_func (key);

        if (hash_table->value_destroy_func)
            hash_table->value_destroy_func ((*node)->value);

        (*node)->value = value;
    } else {
        *node = im_hash_node_new (key, value);
        hash_table->nnodes++;
        IM_HASH_TABLE_RESIZE (hash_table);
    }
}
void
im_hash_table_replace (IMHashTable *hash_table, IMPointer key, IMPointer value)
{
    IMHashNode **node;
  
    _im_return_if_fail (hash_table != NULL);

    node = im_hash_table_lookup_node (hash_table, key);
  
    if (*node) {
        if (hash_table->key_destroy_func)
            hash_table->key_destroy_func ((*node)->key);

        if (hash_table->value_destroy_func)
            hash_table->value_destroy_func ((*node)->value);

        (*node)->key   = key;
        (*node)->value = value;
    } else {
        *node = im_hash_node_new (key, value);
        hash_table->nnodes++;
        IM_HASH_TABLE_RESIZE (hash_table);
    }
}
IMBool
im_hash_table_remove (IMHashTable *hash_table, IMConstPointer key)
{
    IMHashNode **node, *dest;
  
    _im_return_val_if_fail (hash_table, FALSE);
 
    node = im_hash_table_lookup_node (hash_table, key);

    if (*node) {
        dest = *node;
        (*node) = dest->next;
        im_hash_node_destroy (dest, 
                              hash_table->key_destroy_func,
                              hash_table->value_destroy_func);
        hash_table->nnodes--;

        IM_HASH_TABLE_RESIZE (hash_table);

        return TRUE;
    }

    return FALSE;
}
void
im_hash_table_remove_all (IMHashTable *hash_table)
{
    IMInt i;

    _im_return_if_fail (hash_table);

    for (i = 0; i < hash_table->size; ++i) {
        im_hash_nodes_destroy (hash_table->nodes[i],
                               hash_table->key_destroy_func,
                               hash_table->value_destroy_func);
        hash_table->nodes[i] = 0;
    }

    hash_table->nnodes = 0;

    IM_HASH_TABLE_RESIZE (hash_table);
}
IMBool
im_hash_table_steal (IMHashTable *hash_table, IMConstPointer key)
{
    IMHashNode **node, *dest;
  
    _im_return_val_if_fail (hash_table, FALSE);
 
    node = im_hash_table_lookup_node (hash_table, key);

    if (*node) {
        dest = *node;
        (*node) = dest->next;
        im_hash_node_destroy (dest, 0, 0);
        hash_table->nnodes--;

        IM_HASH_TABLE_RESIZE (hash_table);

        return TRUE;
    }

    return FALSE;
}
void
im_hash_table_steal_all (IMHashTable *hash_table)
{
    IMInt i;

    _im_return_if_fail (hash_table);

    for (i = 0; i < hash_table->size; ++i) {
        im_hash_nodes_destroy (hash_table->nodes[i], 0, 0);
        hash_table->nodes[i] = 0;
    }

    hash_table->nnodes = 0;

    IM_HASH_TABLE_RESIZE (hash_table);
}
IMPointer
im_hash_table_lookup (const IMHashTable *hash_table, IMConstPointer key)
{
    IMHashNode *node;

    _im_return_val_if_fail (hash_table, 0);

    node = *im_hash_table_lookup_node (hash_table, key);

    return node ? node->value : 0;
}
IMBool
im_hash_table_lookup_extended (const IMHashTable *hash_table, IMConstPointer lookup_key,
                               IMPointer *orig_key, IMPointer *value)
{
    IMHashNode *node;

    _im_return_val_if_fail (hash_table, FALSE);

    node = *im_hash_table_lookup_node (hash_table, lookup_key);

    if (node) {
        if (orig_key)
            *orig_key = node->key;
        if (value)
            *value = node->value;
        return TRUE;
    } else
        return FALSE;
}
IMBool
im_hash_table_foreach (const IMHashTable *hash_table, IMHRFunc func, IMPointer user_data)
{
    IMHashNode *node;
    IMInt i;

    _im_return_val_if_fail (hash_table, FALSE);
    _im_return_val_if_fail (func, FALSE);

    for (i = 0; i < hash_table->size; ++i)
        for (node = hash_table->nodes[i]; node; node = node->next)
            if (!(*func) (node->key, node->value, user_data))
                return FALSE;
    return TRUE;
}
IMPointer
im_hash_table_find (const IMHashTable *hash_table, IMHRFunc predicate, IMPointer user_data)
{
    IMHashNode *node;
    IMInt i;

    _im_return_val_if_fail (hash_table, 0);
    _im_return_val_if_fail (predicate, 0);

    for (i = 0; i < hash_table->size; i++)
        for (node = hash_table->nodes[i]; node; node = node->next)
            if (predicate (node->key, node->value, user_data))
                return node->value;

    return 0;
}
IMUInt
im_hash_table_foreach_remove (IMHashTable *hash_table, IMHRFunc func, IMPointer user_data)
{
    _im_return_val_if_fail (hash_table, 0);
    _im_return_val_if_fail (func, 0);
  
    return im_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
}
IMUInt
im_hash_table_foreach_steal (IMHashTable *hash_table, IMHRFunc func, IMPointer user_data)
{
    _im_return_val_if_fail (hash_table, 0);
    _im_return_val_if_fail (func, 0);
  
    return im_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
}
IMUInt
im_hash_table_size (const IMHashTable *hash_table)
{
    _im_return_val_if_fail (hash_table, 0);
  
    return hash_table->nnodes;
}

IMHashIterator*
im_hash_table_get_iterator (IMHashTable *hash_table)
{
    IMHashIterator   *iter;
    IMInt             n;

    _im_return_val_if_fail (hash_table, 0);

    iter = im_slice_new (IMHashIterator);

    _im_assert (iter);

    for (n = 0; n < hash_table->size; ++n)
        if (hash_table->nodes [n])
            break;

    iter->table     = hash_table;
    iter->nnodes    = hash_table->nnodes;

    if (n == hash_table->size) {
        iter->head = 0;
        iter->node = 0;
        iter->next_node = 0;
    } else {
        iter->head      = hash_table->nodes + n;
        iter->node      = iter->head;
        iter->next_node = &(*iter->node)->next;
    }

    return iter;
}

void
im_hash_iterator_destroy (IMHashIterator *iterator)
{
    _im_return_if_fail (iterator);

    im_slice_delete (IMHashIterator, iterator);
}

IMBool
im_hash_iterator_equal (const IMHashIterator *iter1, const IMHashIterator *iter2)
{
    _im_return_val_if_fail (iter1, FALSE);
    _im_return_val_if_fail (iter2, FALSE);

    return iter1->table == iter2->table &&
           iter1->head  == iter2->head &&
           iter1->node  == iter2->node;
}

IMBool
im_hash_iterator_next (IMHashIterator *iterator)
{
    _im_return_val_if_fail (iterator, FALSE);
    _im_return_val_if_fail (iterator->table, FALSE);
    _im_return_val_if_fail (iterator->nnodes >= iterator->table->nnodes, FALSE);

    if (!iterator->node || !iterator->next_node || !iterator->head) {
        iterator->head = 0;
        iterator->node = 0;
        iterator->next_node = 0;
        return FALSE;
    }

    while (! *iterator->next_node) {
        if (iterator->head + 1 >= (iterator->table->nodes + iterator->table->size)) {
            iterator->head = 0;
            iterator->node = 0;
            iterator->next_node = 0;
            return FALSE;
        }

        iterator->head ++;
        iterator->next_node = iterator->head;
    }

    _im_assert (iterator->next_node);
    _im_assert (iterator->head);

    iterator->node = iterator->next_node;
    iterator->next_node = & (*iterator->node)->next;

    return TRUE;
}

IMBool
im_hash_iterator_valid (const IMHashIterator *iterator)
{
    return iterator && iterator->table && iterator->head && iterator->node &&
           iterator->next_node && iterator->nnodes >= iterator->table->nnodes;
}

IMBool
im_hash_iterator_get (const IMHashIterator *iterator, IMPointer *key, IMPointer *value)
{
    _im_return_val_if_fail (iterator, FALSE);

    if (iterator->node && *iterator->node) {
        if (key) *key = (*iterator->node)->key;
        if (value) *value = (*iterator->node)->value;
        return TRUE;
    }

    return FALSE;
}

IMPointer
im_hash_iterator_get_key (const IMHashIterator *iterator)
{
    _im_return_val_if_fail (iterator, 0);

    return (iterator->node && *iterator->node) ? (*iterator->node)->key : 0;
}

IMPointer
im_hash_iterator_get_value (const IMHashIterator *iterator)
{
    _im_return_val_if_fail (iterator, 0);

    return (iterator->node && *iterator->node) ? (*iterator->node)->value : 0;
}

void
im_hash_iterator_set_value (IMHashIterator *iterator, IMPointer value)
{
    _im_return_if_fail (iterator);
    _im_return_if_fail (iterator->table);
    _im_return_if_fail (iterator->node);

    if (iterator->node && *iterator->node) {
        if (iterator->table->value_destroy_func)
            iterator->table->value_destroy_func ((*iterator->node)->value);
        (*iterator->node)->value = value;
    }
}

IMBool
im_hash_iterator_remove (IMHashIterator *iterator)
{
    _im_return_val_if_fail (iterator, FALSE);
    _im_return_val_if_fail (iterator->table, FALSE);
    _im_return_val_if_fail (iterator->node, FALSE);

    if (iterator->node && *iterator->node) {
        IMHashNode *dest = *iterator->node;
        (*iterator->node) = dest->next;
        im_hash_node_destroy (dest,
                              iterator->table->key_destroy_func,
                              iterator->table->value_destroy_func);

        iterator->table->nnodes --;

        /* Don't resize hash table */

        return TRUE;
    }

    return FALSE;
}

IMBool
im_hash_iterator_steal (IMHashIterator *iterator)
{
    _im_return_val_if_fail (iterator, FALSE);
    _im_return_val_if_fail (iterator->table, FALSE);
    _im_return_val_if_fail (iterator->node, FALSE);

    if (iterator->node && *iterator->node) {
        IMHashNode *dest = *iterator->node;
        (*iterator->node) = dest->next;
        im_hash_node_destroy (dest, 0, 0);

        iterator->table->nnodes --;

        /* Don't resize hash table */

        return TRUE;
    }

    return FALSE;
}

IMBool
im_str_equal (IMConstPointer v1, IMConstPointer v2)
{
    return strcmp ((const IMChar *) v1, (const IMChar *) v2) == 0;
}
IMUInt
im_str_hash (IMConstPointer v)
{
    /* 31 bit hash function */
    const signed char *p = v;
    IMUInt32 h = *p;

    if (h)
        for (p += 1; *p != '\0'; ++p)
            h = (h << 5) - h + *p;

    return h;
}

IMBool
im_int_equal (IMConstPointer v1, IMConstPointer v2)
{
    return *((const IMInt *)v1) == *((const IMInt *)v2);
}
IMUInt
im_int_hash (IMConstPointer v)
{
    return *(const IMInt *)v;
}

IMUInt
im_direct_hash (IMConstPointer v)
{
    return IM_POINTER_TO_UINT(v);
}
IMBool
im_direct_equal (IMConstPointer v1, IMConstPointer v2)
{
    return v1 == v2;
}

/****************************** Internal functions **************************/
static void
im_hash_table_resize (IMHashTable *hash_table)
{
    IMHashNode **new_nodes;
    IMHashNode *node;
    IMHashNode *next;
    IMUInt       hash_val;
    IMInt        new_size;
    IMInt        i;

    new_size = im_spaced_primes_closest (hash_table->nnodes);
    new_size = IM_CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 
    new_nodes = im_new0 (IMHashNode*, new_size);
  
    for (i = 0; i < hash_table->size; ++i)
        for (node = hash_table->nodes[i]; node; node = next) {
            next = node->next;
            hash_val = (* hash_table->hash_func) (node->key) % new_size;
            node->next = new_nodes[hash_val];
            new_nodes[hash_val] = node;
        }
  
    im_free (hash_table->nodes);
    hash_table->nodes = new_nodes;
    hash_table->size  = new_size;
}
static IMHashNode**
im_hash_table_lookup_node (const IMHashTable *hash_table, IMConstPointer key)
{
    IMHashNode **node;
 
    node = &hash_table->nodes [(* hash_table->hash_func) (key) % hash_table->size];
 
    /* Hash table lookup needs to be fast.
     *  We therefore remove the extra conditional of testing
     *  whether to call the key_equal_func or not from
     *  the inner loop.
     */
    if (hash_table->key_equal_func)
        while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))
            node = &(*node)->next;
    else
        while (*node && (*node)->key != key)
            node = &(*node)->next;
  
    return node;
}
static IMHashNode*
im_hash_node_new (IMPointer key, IMPointer value)
{
    IMHashNode *hash_node = im_slice_new (IMHashNode);
  
    hash_node->key = key;
    hash_node->value = value;
    hash_node->next = NULL;
 
    return hash_node;
}
static void
im_hash_node_destroy (IMHashNode *hash_node, IMDestroyFunc key_destroy_func, IMDestroyFunc value_destroy_func)
{
    if (key_destroy_func)
        key_destroy_func (hash_node->key);
    if (value_destroy_func)
        value_destroy_func (hash_node->value);

    im_slice_delete (IMHashNode, hash_node);
}
static void
im_hash_nodes_destroy (IMHashNode *hash_node, IMDestroyFunc key_destroy_func, IMDestroyFunc value_destroy_func)
{
    while (hash_node) {
        IMHashNode *next = hash_node->next;
        if (key_destroy_func)
            key_destroy_func (hash_node->key);
        if (value_destroy_func)
            value_destroy_func (hash_node->value);
        im_slice_delete (IMHashNode, hash_node);
        hash_node = next;
    }
}
static IMUInt
im_hash_table_foreach_remove_or_steal (IMHashTable        *hash_table,
                                       IMHRFunc            func,
                                       IMPointer           user_data,
                                       IMBool              destroy)
{
    IMHashNode *node, *prev;
    IMInt i;
    IMUInt deleted = 0;

    for (i = 0; i < hash_table->size; i++) {
        restart:

        prev = 0;

        for (node = hash_table->nodes[i]; node; prev = node, node = node->next) {
            if ((* func) (node->key, node->value, user_data)) {
                deleted += 1; 
                hash_table->nnodes -= 1;
                if (prev) {
                    prev->next = node->next;
                    im_hash_node_destroy (node,
                            destroy ? hash_table->key_destroy_func : 0,
                            destroy ? hash_table->value_destroy_func : 0);
                    node = prev;
                } else {
                    hash_table->nodes[i] = node->next;
                    im_hash_node_destroy (node,
                            destroy ? hash_table->key_destroy_func : 0,
                            destroy ? hash_table->value_destroy_func : 0);
                    goto restart;
                }
            }
        }
    }

    IM_HASH_TABLE_RESIZE (hash_table);

    return deleted;
}


/*
vi:ts=4:nowrap:ai:expandtab
*/
